Factorization System Functoriality
   HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, factorization (or factorisation, see English spelling differences) or factoring consists of writing a number or another
mathematical object A mathematical object is an abstract concept arising in mathematics. In the usual language of mathematics, an ''object'' is anything that has been (or could be) formally defined, and with which one may do deductive reasoning and mathematical pr ...
as a product of several ''factors'', usually smaller or simpler objects of the same kind. For example, is a factorization of the
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
, and is a factorization of the
polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
. Factorization is not usually considered meaningful within number systems possessing
division Division or divider may refer to: Mathematics *Division (mathematics), the inverse of multiplication *Division algorithm, a method for computing the result of mathematical division Military *Division (military), a formation typically consisting ...
, such as the
real Real may refer to: Currencies * Brazilian real (R$) * Central American Republic real * Mexican real * Portuguese real * Spanish real * Spanish colonial real Music Albums * ''Real'' (L'Arc-en-Ciel album) (2000) * ''Real'' (Bright album) (2010) ...
or
complex number In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the form ...
s, since any x can be trivially written as (xy)\times(1/y) whenever y is not zero. However, a meaningful factorization for a
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ration ...
or a
rational function In mathematics, a rational function is any function that can be defined by a rational fraction, which is an algebraic fraction such that both the numerator and the denominator are polynomials. The coefficients of the polynomials need not be rat ...
can be obtained by writing it in lowest terms and separately factoring its numerator and denominator. Factorization was first considered by
ancient Greek mathematicians Greek mathematics refers to mathematics texts and ideas stemming from the Archaic through the Hellenistic and Roman periods, mostly extant from the 7th century BC to the 4th century AD, around the shores of the Eastern Mediterranean. Greek mathem ...
in the case of integers. They proved the
fundamental theorem of arithmetic In mathematics, the fundamental theorem of arithmetic, also called the unique factorization theorem and prime factorization theorem, states that every integer greater than 1 can be represented uniquely as a product of prime numbers, up to the ord ...
, which asserts that every positive integer may be factored into a product of
prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s, which cannot be further factored into integers greater than 1. Moreover, this factorization is unique
up to Two Mathematical object, mathematical objects ''a'' and ''b'' are called equal up to an equivalence relation ''R'' * if ''a'' and ''b'' are related by ''R'', that is, * if ''aRb'' holds, that is, * if the equivalence classes of ''a'' and ''b'' wi ...
the order of the factors. Although
integer factorization In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization. When the numbers are suf ...
is a sort of inverse to multiplication, it is much more difficult algorithmically, a fact which is exploited in the
RSA cryptosystem RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem that is widely used for secure data transmission. It is also one of the oldest. The acronym "RSA" comes from the surnames of Ron Rivest, Adi Shamir and Leonard Adleman, who publicly ...
to implement
public-key cryptography Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...
.
Polynomial factorization In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field (mathematics), field or in the integers as the product of irreducible polynomial, irreducible ...
has also been studied for centuries. In elementary algebra, factoring a polynomial reduces the problem of finding its
roots A root is the part of a plant, generally underground, that anchors the plant body, and absorbs and stores water and nutrients. Root or roots may also refer to: Art, entertainment, and media * ''The Root'' (magazine), an online magazine focusing ...
to finding the roots of the factors. Polynomials with coefficients in the integers or in a
field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grass ...
possess the unique factorization property, a version of the fundamental theorem of arithmetic with prime numbers replaced by
irreducible polynomial In mathematics, an irreducible polynomial is, roughly speaking, a polynomial that cannot be factored into the product of two non-constant polynomials. The property of irreducibility depends on the nature of the coefficients that are accepted ...
s. In particular, a
univariate polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example ...
with
complex Complex commonly refers to: * Complexity, the behaviour of a system whose components interact in multiple ways so possible interactions are difficult to describe ** Complex system, a system composed of many components which may interact with each ...
coefficients admits a unique (up to ordering) factorization into
linear polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exampl ...
s: this is a version of the
fundamental theorem of algebra The fundamental theorem of algebra, also known as d'Alembert's theorem, or the d'Alembert–Gauss theorem, states that every non- constant single-variable polynomial with complex coefficients has at least one complex root. This includes polynomia ...
. In this case, the factorization can be done with
root-finding algorithm In mathematics and computing, a root-finding algorithm is an algorithm for finding zeros, also called "roots", of continuous functions. A zero of a function , from the real numbers to real numbers or from the complex numbers to the complex numbers ...
s. The case of polynomials with integer coefficients is fundamental for
computer algebra In mathematics and computer science, computer algebra, also called symbolic computation or algebraic computation, is a scientific area that refers to the study and development of algorithms and software for manipulating mathematical expressions ...
. There are efficient computer
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
s for computing (complete) factorizations within the ring of polynomials with rational number coefficients (see
factorization of polynomials In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same dom ...
). A
commutative ring In mathematics, a commutative ring is a ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra. Complementarily, noncommutative algebra is the study of ring properties that are not sp ...
possessing the unique factorization property is called a
unique factorization domain In mathematics, a unique factorization domain (UFD) (also sometimes called a factorial ring following the terminology of Bourbaki) is a ring in which a statement analogous to the fundamental theorem of arithmetic holds. Specifically, a UFD is an ...
. There are
number system A number is a mathematical object used to count, measure, and label. The original examples are the natural numbers 1, 2, 3, 4, and so forth. Numbers can be represented in language with number words. More universally, individual numbers can ...
s, such as certain rings of algebraic integers, which are not unique factorization domains. However, rings of algebraic integers satisfy the weaker property of
Dedekind domain In abstract algebra, a Dedekind domain or Dedekind ring, named after Richard Dedekind, is an integral domain in which every nonzero proper ideal factors into a product of prime ideals. It can be shown that such a factorization is then necessarily ...
s: ideals factor uniquely into
prime ideal In algebra, a prime ideal is a subset of a ring that shares many important properties of a prime number in the ring of integers. The prime ideals for the integers are the sets that contain all the multiples of a given prime number, together with ...
s. ''Factorization'' may also refer to more general decompositions of a mathematical object into the product of smaller or simpler objects. For example, every function may be factored into the composition of a
surjective function In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of i ...
with an
injective function In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositiv ...
.
Matrices Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** ''The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
possess many kinds of
matrix factorization In the mathematical discipline of linear algebra, a matrix decomposition or matrix factorization is a factorization of a matrix into a product of matrices. There are many different matrix decompositions; each finds use among a particular class of ...
s. For example, every matrix has a unique LUP factorization as a product of a
lower triangular matrix In mathematics, a triangular matrix is a special kind of square matrix. A square matrix is called if all the entries ''above'' the main diagonal are zero. Similarly, a square matrix is called if all the entries ''below'' the main diagonal are ...
with all diagonal entries equal to one, an
upper triangular matrix In mathematics, a triangular matrix is a special kind of square matrix. A square matrix is called if all the entries ''above'' the main diagonal are zero. Similarly, a square matrix is called if all the entries ''below'' the main diagonal are ...
, and a
permutation matrix In mathematics, particularly in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column and 0s elsewhere. Each such matrix, say , represents a permutation of elements and, when ...
; this is a matrix formulation of
Gaussian elimination In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of operations performed on the corresponding matrix of coefficients. This method can also be used ...
.


Integers

By the
fundamental theorem of arithmetic In mathematics, the fundamental theorem of arithmetic, also called the unique factorization theorem and prime factorization theorem, states that every integer greater than 1 can be represented uniquely as a product of prime numbers, up to the ord ...
, every
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
greater than 1 has a unique (up to the order of the factors) factorization into
prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s, which are those integers which cannot be further factorized into the product of integers greater than one. For computing the factorization of an integer , one needs an
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
for finding a
divisor In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
of or deciding that is prime. When such a divisor is found, the repeated application of this algorithm to the factors and gives eventually the complete factorization of . For finding a divisor of , if any, it suffices to test all values of such that and . In fact, if is a divisor of such that , then is a divisor of such that . If one tests the values of in increasing order, the first divisor that is found is necessarily a prime number, and the ''cofactor'' cannot have any divisor smaller than . For getting the complete factorization, it suffices thus to continue the algorithm by searching a divisor of that is not smaller than and not greater than . There is no need to test all values of for applying the method. In principle, it suffices to test only prime divisors. This needs to have a table of prime numbers that may be generated for example with the
sieve of Eratosthenes In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime n ...
. As the method of factorization does essentially the same work as the sieve of Eratosthenes, it is generally more efficient to test for a divisor only those numbers for which it is not immediately clear whether they are prime or not. Typically, one may proceed by testing 2, 3, 5, and the numbers > 5, whose last digit is 1, 3, 7, 9 and the sum of digits is not a multiple of 3. This method works well for factoring small integers, but is inefficient for larger integers. For example,
Pierre de Fermat Pierre de Fermat (; between 31 October and 6 December 1607 – 12 January 1665) was a French mathematician who is given credit for early developments that led to infinitesimal calculus, including his technique of adequality. In particular, he ...
was unable to discover that the 6th
Fermat number In mathematics, a Fermat number, named after Pierre de Fermat, who first studied them, is a positive integer of the form :F_ = 2^ + 1, where ''n'' is a non-negative integer. The first few Fermat numbers are: : 3, 5, 17, 257, 65537, 4294967 ...
: 1 + 2^ = 1 + 2^ = 4\,294\,967\,297 is not a prime number. In fact, applying the above method would require more than , for a number that has 10 
decimal digit A numerical digit (often shortened to just digit) is a single symbol used alone (such as "2") or in combinations (such as "25"), to represent numbers in a positional numeral system. The name "digit" comes from the fact that the ten digits (Latin ...
s. There are more efficient factoring algorithms. However they remain relatively inefficient, as, with the present state of the art, one cannot factorize, even with the more powerful computers, a number of 500 decimal digits that is the product of two randomly chosen prime numbers. This ensures the security of the
RSA cryptosystem RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem that is widely used for secure data transmission. It is also one of the oldest. The acronym "RSA" comes from the surnames of Ron Rivest, Adi Shamir and Leonard Adleman, who publicly ...
, which is widely used for secure
internet The Internet (or internet) is the global system of interconnected computer networks that uses the Internet protocol suite (TCP/IP) to communicate between networks and devices. It is a '' network of networks'' that consists of private, pub ...
communication.


Example

For factoring into primes: * Start with division by 2: the number is even, and . Continue with 693, and 2 as a first divisor candidate. * 693 is odd (2 is not a divisor), but is a multiple of 3: one has and . Continue with 231, and 3 as a first divisor candidate. * 231 is also a multiple of 3: one has , and thus . Continue with 77, and 3 as a first divisor candidate. * 77 is not a multiple of 3, since the sum of its digits is 14, not a multiple of 3. It is also not a multiple of 5 because its last digit is 7. The next odd divisor to be tested is 7. One has , and thus . This shows that 7 is prime (easy to test directly). Continue with 11, and 7 as a first divisor candidate. * As , one has finished. Thus 11 is prime, and the prime factorization is : .


Expressions

Manipulating expressions is the basis of
algebra Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics. Elementary a ...
. Factorization is one of the most important methods for expression manipulation for several reasons. If one can put an
equation In mathematics, an equation is a formula that expresses the equality of two expressions, by connecting them with the equals sign . The word ''equation'' and its cognates in other languages may have subtly different meanings; for example, in ...
in a factored form , then the problem of solving the equation splits into two independent (and generally easier) problems and . When an expression can be factored, the factors are often much simpler, and may thus offer some insight on the problem. For example, :x^3-ax^2-bx^2-cx^2+ abx+acx+bcx-abc having 16 multiplications, 4 subtractions and 3 additions, may be factored into the much simpler expression :(x-a)(x-b)(x-c), with only two multiplications and three subtractions. Moreover, the factored form immediately gives
roots A root is the part of a plant, generally underground, that anchors the plant body, and absorbs and stores water and nutrients. Root or roots may also refer to: Art, entertainment, and media * ''The Root'' (magazine), an online magazine focusing ...
''x'' = ''a'',''b'',''c'' as the roots of the polynomial. On the other hand, factorization is not always possible, and when it is possible, the factors are not always simpler. For example, x^-1 can be factored into two irreducible factors x-1 and x^+x^+\cdots+x^2+x+1. Various methods have been developed for finding factorizations; some are described
below Below may refer to: *Earth *Ground (disambiguation) *Soil *Floor *Bottom (disambiguation) Bottom may refer to: Anatomy and sex * Bottom (BDSM), the partner in a BDSM who takes the passive, receiving, or obedient role, to that of the top or ...
. Solving
algebraic equation In mathematics, an algebraic equation or polynomial equation is an equation of the form :P = 0 where ''P'' is a polynomial with coefficients in some field, often the field of the rational numbers. For many authors, the term ''algebraic equation'' ...
s may be viewed as a problem of
polynomial factorization In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field (mathematics), field or in the integers as the product of irreducible polynomial, irreducible ...
. In fact, the
fundamental theorem of algebra The fundamental theorem of algebra, also known as d'Alembert's theorem, or the d'Alembert–Gauss theorem, states that every non- constant single-variable polynomial with complex coefficients has at least one complex root. This includes polynomia ...
can be stated as follows: every
polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
in of degree with
complex Complex commonly refers to: * Complexity, the behaviour of a system whose components interact in multiple ways so possible interactions are difficult to describe ** Complex system, a system composed of many components which may interact with each ...
coefficients may be factorized into linear factors x-a_i, for , where the s are the roots of the polynomial. Even though the structure of the factorization is known in these cases, the s generally cannot be computed in terms of radicals (''n''th roots), by the
Abel–Ruffini theorem In mathematics, the Abel–Ruffini theorem (also known as Abel's impossibility theorem) states that there is no solution in radicals to general polynomial equations of degree five or higher with arbitrary coefficients. Here, ''general'' means th ...
. In most cases, the best that can be done is computing approximate values of the roots with a
root-finding algorithm In mathematics and computing, a root-finding algorithm is an algorithm for finding zeros, also called "roots", of continuous functions. A zero of a function , from the real numbers to real numbers or from the complex numbers to the complex numbers ...
.


History of factorization of expressions

The systematic use of algebraic manipulations for simplifying expressions (more specifically
equation In mathematics, an equation is a formula that expresses the equality of two expressions, by connecting them with the equals sign . The word ''equation'' and its cognates in other languages may have subtly different meanings; for example, in ...
s)) may be dated to 9th century, with
al-Khwarizmi Muḥammad ibn Mūsā al-Khwārizmī ( ar, محمد بن موسى الخوارزمي, Muḥammad ibn Musā al-Khwārazmi; ), or al-Khwarizmi, was a Persian polymath from Khwarazm, who produced vastly influential works in mathematics, astronom ...
's book ''
The Compendious Book on Calculation by Completion and Balancing ''The Compendious Book on Calculation by Completion and Balancing'' ( ar, كتاب المختصر في حساب الجبر والمقابلة, ; la, Liber Algebræ et Almucabola), also known as ''Al-Jabr'' (), is an Arabic mathematical treati ...
'', which is titled with two such types of manipulation. However, even for solving
quadratic equation In algebra, a quadratic equation () is any equation that can be rearranged in standard form as ax^2 + bx + c = 0\,, where represents an unknown (mathematics), unknown value, and , , and represent known numbers, where . (If and then the equati ...
s, the factoring method was not used before Harriot's work published in 1631, ten years after his death. In his book ''Artis Analyticae Praxis ad Aequationes Algebraicas Resolvendas'', Harriot drew tables for addition, subtraction, multiplication and division of
monomial In mathematics, a monomial is, roughly speaking, a polynomial which has only one term. Two definitions of a monomial may be encountered: # A monomial, also called power product, is a product of powers of variables with nonnegative integer exponent ...
s,
binomial Binomial may refer to: In mathematics *Binomial (polynomial), a polynomial with two terms * Binomial coefficient, numbers appearing in the expansions of powers of binomials *Binomial QMF, a perfect-reconstruction orthogonal wavelet decomposition ...
s, and
trinomial In elementary algebra, a trinomial is a polynomial consisting of three terms or monomials. Examples of trinomial expressions # 3x + 5y + 8z with x, y, z variables # 3t + 9s^2 + 3y^3 with t, s, y variables # 3ts + 9t + 5s with t, s variables # a ...
s. Then, in a second section, he set up the equation , and showed that this matches the form of multiplication he had previously provided, giving the factorization .


General methods

The following methods apply to any expression that is a sum, or that may be transformed into a sum. Therefore, they are most often applied to
polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
s, though they also may be applied when the terms of the sum are not
monomial In mathematics, a monomial is, roughly speaking, a polynomial which has only one term. Two definitions of a monomial may be encountered: # A monomial, also called power product, is a product of powers of variables with nonnegative integer exponent ...
s, that is, the terms of the sum are a product of variables and constants.


Common factor

It may occur that all terms of a sum are products and that some factors are common to all terms. In this case, the
distributive law In mathematics, the distributive property of binary operations generalizes the distributive law, which asserts that the equality x \cdot (y + z) = x \cdot y + x \cdot z is always true in elementary algebra. For example, in elementary arithmetic, ...
allows factoring out this common factor. If there are several such common factors, it is preferable to divide out the greatest such common factor. Also, if there are integer coefficients, one may factor out the
greatest common divisor In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
of these coefficients. For example, :6x^3y^2 + 8x^4y^3 - 10x^5y^3 = 2x^3y^2(3 + 4xy -5x^2y), since 2 is the greatest common divisor of 6, 8, and 10, and x^3y^2 divides all terms.


Grouping

Grouping terms may allow using other methods for getting a factorization. For example, to factor : 4x^2+20x+3xy+15y, one may remark that the first two terms have a common factor , and the last two terms have the common factor . Thus : 4x^2+20x+3xy+15y = (4x^2+20x)+(3xy+15y) = 4x(x+5)+3y(x+5). Then a simple inspection shows the common factor , leading to the factorization : 4x^2+20x+3xy+15y = (4x+3y)(x+5). In general, this works for sums of 4 terms that have been obtained as the product of two binomials. Although not frequently, this may work also for more complicated examples.


Adding and subtracting terms

Sometimes, some term grouping reveals part of a recognizable pattern. It is then useful to add and subtract terms to complete the pattern. A typical use of this is the
completing the square : In elementary algebra, completing the square is a technique for converting a quadratic polynomial of the form :ax^2 + bx + c to the form :a(x-h)^2 + k for some values of ''h'' and ''k''. In other words, completing the square places a perfe ...
method for getting the
quadratic formula In elementary algebra, the quadratic formula is a formula that provides the solution(s) to a quadratic equation. There are other ways of solving a quadratic equation instead of using the quadratic formula, such as factoring (direct factoring, gr ...
. Another example is the factorization of x^4 + 1. If one introduces the non-real square root of –1, commonly denoted , then one has a
difference of squares In mathematics, the difference of two squares is a squared (multiplied by itself) number subtracted from another squared number. Every difference of squares may be factored according to the identity :a^2-b^2 = (a+b)(a-b) in elementary algebra. P ...
:x^4+1=(x^2+i)(x^2-i). However, one may also want a factorization with
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
coefficients. By adding and subtracting 2x^2, and grouping three terms together, one may recognize the square of a
binomial Binomial may refer to: In mathematics *Binomial (polynomial), a polynomial with two terms * Binomial coefficient, numbers appearing in the expansions of powers of binomials *Binomial QMF, a perfect-reconstruction orthogonal wavelet decomposition ...
: :x^4+1 = (x^4+2x^2+1)-2x^2 = (x^2+1)^2 - \left(x\sqrt2\right)^2 =\left(x^2+x\sqrt2+1\right)\left(x^2-x\sqrt2+1\right). Subtracting and adding 2x^2 also yields the factorization: :x^4+1 = (x^4-2x^2+1)+2x^2 = (x^2-1)^2 + \left(x\sqrt2\right)^2 =\left(x^2+x\sqrt-1\right)\left(x^2-x\sqrt-1\right). These factorizations work not only over the complex numbers, but also over any
field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grass ...
, where either –1, 2 or –2 is a square. In a
finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
, the product of two non-squares is a square; this implies that the
polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
x^4 + 1, which is
irreducible In philosophy, systems theory, science, and art, emergence occurs when an entity is observed to have properties its parts do not have on their own, properties or behaviors that emerge only when the parts interact in a wider whole. Emergence ...
over the integers, is reducible modulo every
prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
. For example, :x^4 + 1 \equiv (x+1)^4 \pmod 2; :x^4 + 1 \equiv (x^2+x-1)(x^2-x-1) \pmod 3,\qquadsince 1^2 \equiv -2 \pmod 3; :x^4 + 1 \equiv (x^2+2)(x^2-2) \pmod 5,\qquadsince 2^2 \equiv -1 \pmod 5; :x^4 + 1 \equiv (x^2+3x+1)(x^2-3x+1) \pmod 7,\qquadsince 3^2 \equiv 2 \pmod 7.


Recognizable patterns

Many identities provide an equality between a sum and a product. The above methods may be used for letting the sum side of some identity appear in an expression, which may therefore be replaced by a product. Below are identities whose left-hand sides are commonly used as patterns (this means that the variables and that appear in these identities may represent any subexpression of the expression that has to be factorized). *;
Difference of two squares In mathematics, the difference of two squares is a squared (multiplied by itself) number subtracted from another squared number. Every difference of squares may be factored according to the identity :a^2-b^2 = (a+b)(a-b) in elementary algebra. ...
:: E^2 - F^2 = (E+F)(E-F) :For example, ::\begin a^2 + &2ab + b^2 - x^2 +2xy - y^2 \\ &= (a^2 + 2ab + b^2) - (x^2 -2xy + y^2) \\ &= (a+b)^2 - (x -y)^2 \\ &= (a+b + x -y)(a+b -x + y). \end *;Sum/difference of two cubes :: E^3 + F^3 = (E + F)(E^2 - EF + F^2) :: E^3 - F^3 = (E - F)(E^2 + EF + F^2) *;Difference of two fourth powers ::\begin E^4 - F^4 &= (E^2 + F^2)(E^2 - F^2) \\ &= (E^2 + F^2)(E + F)(E - F) \end *;Sum/difference of two th powers :In the following identities, the factors may often be further factorized: :*;Difference, even exponent ::E^-F^= (E^n+F^n)(E^n-F^n) :*;Difference, even or odd exponent :: E^n - F^n = (E-F)(E^ + E^F + E^F^2 + \cdots + EF^ + F^ ) ::This is an example showing that the factors may be much larger than the sum that is factorized. :*;Sum, odd exponent :: E^n + F^n = (E+F)(E^ - E^F + E^F^2 - \cdots - EF^ + F^ ) ::(obtained by changing by in the preceding formula) :*;Sum, even exponent ::If the exponent is a power of two then the expression cannot, in general, be factorized without introducing
complex numbers In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the form a ...
(if and contain complex numbers, this may be not the case). If ''n'' has an odd divisor, that is if with odd, one may use the preceding formula (in "Sum, odd exponent") applied to (E^q)^p+(F^q)^p. *;Trinomials and cubic formulas ::: \begin &x^2 + y^2 + z^2 + 2(xy +yz+xz)= (x + y+ z)^2 \\ &x^3 + y^3 + z^3 - 3xyz = (x + y + z)(x^2 + y^2 + z^2 - xy - xz - yz)\\ &x^3 + y^3 + z^3 + 3x^2(y + z) +3y^2(x+z) + 3z^2(x+y) + 6xyz = (x + y+z)^3 \\ &x^4 + x^2y^2 + y^4 = (x^2 + xy+y^2)(x^2 - xy + y^2). \end *;Binomial expansions :The
binomial theorem In elementary algebra, the binomial theorem (or binomial expansion) describes the algebraic expansion of powers of a binomial. According to the theorem, it is possible to expand the polynomial into a sum involving terms of the form , where the ...
supplies patterns that can easily be recognized from the integers that appear in them :In low degree: :: a^2 + 2ab + b^2 = (a + b)^2 :: a^2 - 2ab + b^2 = (a - b)^2 :: a^3 + 3a^2b + 3ab^2 + b^3 = (a+b)^3 :: a^3 - 3a^2b + 3ab^2 - b^3 = (a-b)^3 :More generally, the coefficients of the expanded forms of (a+b)^n and (a-b)^n are the
binomial coefficient In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...
s, that appear in the th row of
Pascal's triangle In mathematics, Pascal's triangle is a triangular array of the binomial coefficients that arises in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Blaise Pascal, although ot ...
.


Roots of unity

The th
roots of unity In mathematics, a root of unity, occasionally called a de Moivre number, is any complex number that yields 1 when raised to some positive integer power . Roots of unity are used in many branches of mathematics, and are especially important in ...
are the
complex number In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the form ...
s each of which is a
root In vascular plants, the roots are the organs of a plant that are modified to provide anchorage for the plant and take in water and nutrients into the plant body, which allows plants to grow taller and faster. They are most often below the sur ...
of the polynomial x^n-1. They are thus the numbers :e^=\cos \tfracn +i\sin \tfracn for k=0, \ldots, n-1. It follows that for any two expressions and , one has: :E^n-F^n= (E-F)\prod_^ \left(E-F e^\right) :E^+F^=\prod_^ \left(E-F e^\right) \qquad \text n \text :E^+F^=(E+F)\prod_^\left(E+F e^\right) \qquad \text n \text If and are real expressions, and one wants real factors, one has to replace every pair of
complex conjugate In mathematics, the complex conjugate of a complex number is the number with an equal real part and an imaginary part equal in magnitude but opposite in sign. That is, (if a and b are real, then) the complex conjugate of a + bi is equal to a - ...
factors by its product. As the complex conjugate of e^ is e^, and :\left(a-be^\right)\left(a-be^\right)= a^2-ab\left(e^+e^\right)+b^2e^e^= a^2-2ab\cos\,\alpha +b^2, one has the following real factorizations (one passes from one to the other by changing into or , and applying the usual trigonometric formulas: :\beginE^-F^&= (E-F)(E+F)\prod_^ \left(E^2-2EF \cos\,\tfracn +F^2\right)\\ &=(E-F)(E+F)\prod_^ \left(E^2+2EF \cos\,\tfracn +F^2\right)\end : \beginE^ + F^ &= \prod_^n \left(E^2 + 2EF\cos\,\tfrac+F^2\right)\\ &=\prod_^n \left(E^2 - 2EF\cos\,\tfrac+F^2\right) \end The cosines that appear in these factorizations are
algebraic number An algebraic number is a number that is a root of a non-zero polynomial in one variable with integer (or, equivalently, rational) coefficients. For example, the golden ratio, (1 + \sqrt)/2, is an algebraic number, because it is a root of the po ...
s, and may be expressed in terms of radicals (this is possible because their
Galois group In mathematics, in the area of abstract algebra known as Galois theory, the Galois group of a certain type of field extension is a specific group associated with the field extension. The study of field extensions and their relationship to the pol ...
is cyclic); however, these radical expressions are too complicated to be used, except for low values of . For example, : a^4 + b^4 = (a^2 - \sqrt 2 ab + b^2)(a^2 + \sqrt 2 ab + b^2). : a^5 - b^5 = (a - b)\left(a^2 + \frac2 ab + b^2\right)\left(a^2 +\frac2 ab + b^2\right), : a^5 + b^5 = (a + b)\left(a^2 - \frac2 ab + b^2\right)\left(a^2 -\frac2 ab + b^2\right), Often one wants a factorization with rational coefficients. Such a factorization involves
cyclotomic polynomial In mathematics, the ''n''th cyclotomic polynomial, for any positive integer ''n'', is the unique irreducible polynomial with integer coefficients that is a divisor of x^n-1 and is not a divisor of x^k-1 for any Its roots are all ''n''th primiti ...
s. To express rational factorizations of sums and differences or powers, we need a notation for the homogenization of a polynomial: if P(x)=a_0x^n+a_ix^ +\cdots +a_n, its ''homogenization'' is the bivariate polynomial \overline P(x,y)=a_0x^n+a_ix^y +\cdots +a_ny^n. Then, one has :E^n-F^n=\prod_\overline Q_n(E,F), :E^n+F^n=\prod_\overline Q_n(E,F), where the products are taken over all divisors of , or all divisors of that do not divide , and Q_n(x) is the th cyclotomic polynomial. For example, :a^6-b^6= \overline Q_1(a,b)\overline Q_2(a,b)\overline Q_3(a,b)\overline Q_6(a,b)=(a-b)(a+b)(a^2-ab+b^2)(a^2+ab+b^2), :a^6+b^6=\overline Q_4(a,b)\overline Q_(a,b) = (a^2+b^2)(a^4-a^2b^2+b^4), since the divisors of 6 are 1, 2, 3, 6, and the divisors of 12 that do not divide 6 are 4 and 12.


Polynomials

For polynomials, factorization is strongly related with the problem of solving
algebraic equation In mathematics, an algebraic equation or polynomial equation is an equation of the form :P = 0 where ''P'' is a polynomial with coefficients in some field, often the field of the rational numbers. For many authors, the term ''algebraic equation'' ...
s. An algebraic equation has the form :P(x)\ \,\stackrel\ \,a_0x^n+a_1x^+\cdots+a_n=0, where is a polynomial in with a_0\ne 0. A solution of this equation (also called a
root In vascular plants, the roots are the organs of a plant that are modified to provide anchorage for the plant and take in water and nutrients into the plant body, which allows plants to grow taller and faster. They are most often below the sur ...
of the polynomial) is a value of such that :P(r)=0. If P(x)=Q(x)R(x) is a factorization of as a product of two polynomials, then the roots of are the
union Union commonly refers to: * Trade union, an organization of workers * Union (set theory), in mathematics, a fundamental operation on sets Union may also refer to: Arts and entertainment Music * Union (band), an American rock group ** ''Un ...
of the roots of and the roots of . Thus solving is reduced to the simpler problems of solving and . Conversely, the
factor theorem In algebra, the factor theorem is a theorem linking factors and zeros of a polynomial. It is a special case of the polynomial remainder theorem. The factor theorem states that a polynomial f(x) has a factor (x - \alpha) if and only if f(\alpha)=0 ...
asserts that, if is a root of , then may be factored as :P(x)=(x-r)Q(x), where is the quotient of
Euclidean division In arithmetic, Euclidean division – or division with remainder – is the process of dividing one integer (the dividend) by another (the divisor), in a way that produces an integer quotient and a natural number remainder strictly smaller than ...
of by the linear (degree one) factor . If the coefficients of are
real Real may refer to: Currencies * Brazilian real (R$) * Central American Republic real * Mexican real * Portuguese real * Spanish real * Spanish colonial real Music Albums * ''Real'' (L'Arc-en-Ciel album) (2000) * ''Real'' (Bright album) (2010) ...
or
complex Complex commonly refers to: * Complexity, the behaviour of a system whose components interact in multiple ways so possible interactions are difficult to describe ** Complex system, a system composed of many components which may interact with each ...
numbers, the
fundamental theorem of algebra The fundamental theorem of algebra, also known as d'Alembert's theorem, or the d'Alembert–Gauss theorem, states that every non- constant single-variable polynomial with complex coefficients has at least one complex root. This includes polynomia ...
asserts that has a real or complex root. Using the factor theorem recursively, it results that :P(x)=a_0(x-r_1)\cdots (x-r_n), where r_1, \ldots, r_n are the real or complex roots of , with some of them possibly repeated. This complete factorization is unique
up to Two Mathematical object, mathematical objects ''a'' and ''b'' are called equal up to an equivalence relation ''R'' * if ''a'' and ''b'' are related by ''R'', that is, * if ''aRb'' holds, that is, * if the equivalence classes of ''a'' and ''b'' wi ...
the order of the factors. If the coefficients of are real, one generally wants a factorization where factors have real coefficients. In this case, the complete factorization may have some quadratic (degree two) factors. This factorization may easily be deduced from the above complete factorization. In fact, if is a non-real root of , then its
complex conjugate In mathematics, the complex conjugate of a complex number is the number with an equal real part and an imaginary part equal in magnitude but opposite in sign. That is, (if a and b are real, then) the complex conjugate of a + bi is equal to a - ...
is also a root of . So, the product :(x-r)(x-s) = x^2-(r+s)x+rs = x^2-2ax+a^2+b^2 is a factor of with real coefficients. Repeating this for all non-real factors gives a factorization with linear or quadratic real factors. For computing these real or complex factorizations, one needs the roots of the polynomial, which may not be computed exactly, and only approximated using
root-finding algorithm In mathematics and computing, a root-finding algorithm is an algorithm for finding zeros, also called "roots", of continuous functions. A zero of a function , from the real numbers to real numbers or from the complex numbers to the complex numbers ...
s. In practice, most algebraic equations of interest have
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
or
rational Rationality is the quality of being guided by or based on reasons. In this regard, a person acts rationally if they have a good reason for what they do or a belief is rational if it is based on strong evidence. This quality can apply to an abi ...
coefficients, and one may want a factorization with factors of the same kind. The
fundamental theorem of arithmetic In mathematics, the fundamental theorem of arithmetic, also called the unique factorization theorem and prime factorization theorem, states that every integer greater than 1 can be represented uniquely as a product of prime numbers, up to the ord ...
may be generalized to this case, stating that polynomials with integer or rational coefficients have the unique factorization property. More precisely, every polynomial with rational coefficients may be factorized in a product :P(x)=q\,P_1(x)\cdots P_k(x), where is a rational number and P_1(x), \ldots, P_k(x) are non-constant polynomials with integer coefficients that are
irreducible In philosophy, systems theory, science, and art, emergence occurs when an entity is observed to have properties its parts do not have on their own, properties or behaviors that emerge only when the parts interact in a wider whole. Emergence ...
and primitive; this means that none of the P_i(x) may be written as the product two polynomials (with integer coefficients) that are neither 1 nor –1 (integers are considered as polynomials of degree zero). Moreover, this factorization is unique up to the order of the factors and the signs of the factors. There are efficient
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
s for computing this factorization, which are implemented in most
computer algebra In mathematics and computer science, computer algebra, also called symbolic computation or algebraic computation, is a scientific area that refers to the study and development of algorithms and software for manipulating mathematical expressions ...
systems. See
Factorization of polynomials In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same dom ...
. Unfortunately, these algorithms are too complicated to use for paper-and-pencil computations. Besides the heuristics above, only a few methods are suitable for hand computations, which generally work only for polynomials of low degree, with few nonzero coefficients. The main such methods are described in next subsections.


Primitive-part & content factorization

Every polynomial with
rational Rationality is the quality of being guided by or based on reasons. In this regard, a person acts rationally if they have a good reason for what they do or a belief is rational if it is based on strong evidence. This quality can apply to an abi ...
coefficients, may be factorized, in a unique way, as the product of a rational number and a polynomial with integer coefficients, which is primitive (that is, the
greatest common divisor In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
of the coefficients is 1), and has a positive leading coefficient (coefficient of the term of the highest degree). For example: :-10x^2 + 5x + 5 = (-5)\cdot (2x^2 - x - 1) :\fracx^5 + \frac x^2 + 2x + 1 = \frac ( 2x^5 + 21x^2 + 12x + 6) In this factorization, the rational number is called the
content Content or contents may refer to: Media * Content (media), information or experience provided to audience or end-users by publishers or media producers ** Content industry, an umbrella term that encompasses companies owning and providing mas ...
, and the primitive polynomial is the primitive part. The computation of this factorization may be done as follows: firstly, reduce all coefficients to a common denominator, for getting the quotient by an integer of a polynomial with integer coefficients. Then one divides out the greater common divisor of the coefficients of this polynomial for getting the primitive part, the content being p/q. Finally, if needed, one changes the signs of and all coefficients of the primitive part. This factorization may produce a result that is larger than the original polynomial (typically when there are many
coprime In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
denominators), but, even when this is the case, the primitive part is generally easier to manipulate for further factorization.


Using the factor theorem

The factor theorem states that, if is a
root In vascular plants, the roots are the organs of a plant that are modified to provide anchorage for the plant and take in water and nutrients into the plant body, which allows plants to grow taller and faster. They are most often below the sur ...
of a
polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
:P(x)=a_0x^n+a_1x^+\cdots+a_x+a_n, meaning , then there is a factorization :P(x)=(x-r)Q(x), where :Q(x)=b_0x^+\cdots+b_x+b_, with a_0=b_0. Then
polynomial long division In algebra, polynomial long division is an algorithm for dividing a polynomial by another polynomial of the same or lower degree, a generalized version of the familiar arithmetic technique called long division. It can be done easily by hand, becaus ...
or
synthetic division In algebra, synthetic division is a method for manually performing Euclidean division of polynomials, with less writing and fewer calculations than long division. It is mostly taught for division by linear monic polynomials (known as the Ruffini ...
give: :b_i=a_0r^i +\cdots+a_r+a_i \ \text\ i = 1,\ldots,n1. This may be useful when one knows or can guess a root of the polynomial. For example, for P(x) = x^3 - 3x + 2, one may easily see that the sum of its coefficients is 0, so is a root. As , and r^2 +0r-3=-2, one has :x^3 - 3x + 2 = (x - 1)(x^2 + x - 2).


Rational roots

For polynomials with rational number coefficients, one may search for roots which are rational numbers. Primitive part-content factorization (see above) reduces the problem of searching for rational roots to the case of polynomials with integer coefficients having no non-trivial
common divisor In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
. If x=\tfrac pq is a rational root of such a polynomial :P(x)=a_0x^n+a_1x^+\cdots+a_x+a_n, the factor theorem shows that one has a factorization :P(x)=(qx-p)Q(x), where both factors have integer coefficients (the fact that has integer coefficients results from the above formula for the quotient of by x-p/q). Comparing the coefficients of degree and the constant coefficients in the above equality shows that, if \tfrac pq is a rational root in
reduced form In statistics, and particularly in econometrics, the reduced form of a system of equations is the result of solving the system for the endogenous variables. This gives the latter as functions of the exogenous variables, if any. In econometrics, the ...
, then is a divisor of a_0, and is a divisor of a_n. Therefore, there is a finite number of possibilities for and , which can be systematically examined. For example, if the polynomial :P(x)=2x^3 - 7x^2 + 10x - 6 has a rational root \tfrac pq with , then must divide 6; that is p\in\, and must divide 2, that is q\in\. Moreover, if , all terms of the polynomial are negative, and, therefore, a root cannot be negative. That is, one must have :\tfrac pq \in \. A direct computation shows that only \tfrac 32 is a root, so there can be no other rational root. Applying the factor theorem leads finally to the factorization 2x^3 - 7x^2 + 10x - 6 = (2x -3)(x^2 -2x + 2).


Quadratic ac method

The above method may be adapted for
quadratic polynomial In mathematics, a quadratic polynomial is a polynomial of degree two in one or more variables. A quadratic function is the polynomial function defined by a quadratic polynomial. Before 20th century, the distinction was unclear between a polynomia ...
s, leading to the ''ac method'' of factorization. Consider the quadratic polynomial :P(x)=ax^2 + bx + c with integer coefficients. If it has a rational root, its denominator must divide evenly and it may be written as a possibly
reducible fraction An irreducible fraction (or fraction in lowest terms, simplest form or reduced fraction) is a fraction in which the numerator and denominator are integers that have no other common divisors than 1 (and −1, when negative numbers are considered). ...
r_1 = \tfrac ra. By
Vieta's formulas In mathematics, Vieta's formulas relate the coefficients of a polynomial to sums and products of its roots. They are named after François Viète (more commonly referred to by the Latinised form of his name, "Franciscus Vieta"). Basic formulas A ...
, the other root r_2 is :r_2 = -\frac ba - r_1 = -\frac ba-\frac ra =-\fraca = \frac sa, with s=-(b+r). Thus the second root is also rational, and Vieta's second formula r_1 r_2=\frac ca gives :\frac sa\frac ra =\frac ca, that is :rs=ac\quad \text\quad r+s=-b. Checking all pairs of integers whose product is gives the rational roots, if any. In summary, if ax^2 +bx+c has rational roots there are integers and such rs=ac and r+s=-b (a finite number of cases to test), and the roots are \tfrac ra and \tfrac sa. In other words, one has the factorization :a(ax^2+bx+c) = (ax-r)(ax-s). For example, let consider the quadratic polynomial :6x^2 + 13x + 6. Inspection of the factors of leads to , giving the two roots :r_1 = -\frac 46 =-\frac 23 \quad \text \quad r_2 = -\frac96 = -\frac 32, and the factorization : 6x^2 + 13x + 6 = 6(x+\tfrac 23)(x+\tfrac 32)= (3x+2)(2x+3).


Using formulas for polynomial roots

Any univariate
quadratic polynomial In mathematics, a quadratic polynomial is a polynomial of degree two in one or more variables. A quadratic function is the polynomial function defined by a quadratic polynomial. Before 20th century, the distinction was unclear between a polynomia ...
ax^2+bx+c can be factored using the
quadratic formula In elementary algebra, the quadratic formula is a formula that provides the solution(s) to a quadratic equation. There are other ways of solving a quadratic equation instead of using the quadratic formula, such as factoring (direct factoring, gr ...
: : ax^2 + bx + c = a(x - \alpha)(x - \beta) = a\left(x - \frac\right) \left(x - \frac\right), where \alpha and \beta are the two
roots A root is the part of a plant, generally underground, that anchors the plant body, and absorbs and stores water and nutrients. Root or roots may also refer to: Art, entertainment, and media * ''The Root'' (magazine), an online magazine focusing ...
of the polynomial. If are all
real Real may refer to: Currencies * Brazilian real (R$) * Central American Republic real * Mexican real * Portuguese real * Spanish real * Spanish colonial real Music Albums * ''Real'' (L'Arc-en-Ciel album) (2000) * ''Real'' (Bright album) (2010) ...
, the factors are real if and only if the
discriminant In mathematics, the discriminant of a polynomial is a quantity that depends on the coefficients and allows deducing some properties of the roots without computing them. More precisely, it is a polynomial function of the coefficients of the origi ...
b^2-4ac is non-negative. Otherwise, the quadratic polynomial cannot be factorized into non-constant real factors. The quadratic formula is valid when the coefficients belong to any
field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grass ...
of characteristic different from two, and, in particular, for coefficients in a
finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
with an odd number of elements. There are also formulas for roots of cubic and quartic polynomials, which are, in general, too complicated for practical use. The
Abel–Ruffini theorem In mathematics, the Abel–Ruffini theorem (also known as Abel's impossibility theorem) states that there is no solution in radicals to general polynomial equations of degree five or higher with arbitrary coefficients. Here, ''general'' means th ...
shows that there are no general root formulas in terms of radicals for polynomials of degree five or higher.


Using relations between roots

It may occur that one knows some relationship between the roots of a polynomial and its coefficients. Using this knowledge may help factoring the polynomial and finding its roots.
Galois theory In mathematics, Galois theory, originally introduced by Évariste Galois, provides a connection between field theory and group theory. This connection, the fundamental theorem of Galois theory, allows reducing certain problems in field theory to ...
is based on a systematic study of the relations between roots and coefficients, that include
Vieta's formulas In mathematics, Vieta's formulas relate the coefficients of a polynomial to sums and products of its roots. They are named after François Viète (more commonly referred to by the Latinised form of his name, "Franciscus Vieta"). Basic formulas A ...
. Here, we consider the simpler case where two roots x_1 and x_2 of a polynomial P(x) satisfy the relation :x_2=Q(x_1), where is a polynomial. This implies that x_1 is a common root of P(Q(x)) and P(x). It is therefore a root of the
greatest common divisor In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
of these two polynomials. It follows that this greatest common divisor is a non constant factor of P(x).
Euclidean algorithm for polynomials In algebra, the greatest common divisor (frequently abbreviated as GCD) of two polynomials is a polynomial, of the highest possible degree, that is a factor of both the two original polynomials. This concept is analogous to the greatest common di ...
allows computing this greatest common factor. For example, if one know or guess that: P(x)=x^3 -5x^2 -16x +80 has two roots that sum to zero, one may apply Euclidean algorithm to P(x) and P(-x). The first division step consists in adding P(x) to P(-x), giving the
remainder In mathematics, the remainder is the amount "left over" after performing some computation. In arithmetic, the remainder is the integer "left over" after dividing one integer by another to produce an integer quotient (integer division). In algebr ...
of :-10(x^2-16). Then, dividing P(x) by x^2-16 gives zero as a new remainder, and as a quotient, leading to the complete factorization :x^3 - 5x^2 - 16x + 80 = (x -5)(x-4)(x+4).


Unique factorization domains

The integers and the polynomials over a
field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grass ...
share the property of unique factorization, that is, every nonzero element may be factored into a product of an invertible element (a
unit Unit may refer to: Arts and entertainment * UNIT, a fictional military organization in the science fiction television series ''Doctor Who'' * Unit of action, a discrete piece of action (or beat) in a theatrical presentation Music * ''Unit'' (alb ...
, ±1 in the case of integers) and a product of
irreducible element In algebra, an irreducible element of a domain is a non-zero element that is not invertible (that is, is not a unit), and is not the product of two non-invertible elements. Relationship with prime elements Irreducible elements should not be confus ...
s (
prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s, in the case of integers), and this factorization is unique up to rearranging the factors and shifting units among the factors.
Integral domain In mathematics, specifically abstract algebra, an integral domain is a nonzero commutative ring in which the product of any two nonzero elements is nonzero. Integral domains are generalizations of the ring of integers and provide a natural set ...
s which share this property are called
unique factorization domain In mathematics, a unique factorization domain (UFD) (also sometimes called a factorial ring following the terminology of Bourbaki) is a ring in which a statement analogous to the fundamental theorem of arithmetic holds. Specifically, a UFD is an ...
s (UFD).
Greatest common divisor In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
s exist in UFDs, and conversely, every integral domain in which greatest common divisors exist is an UFD. Every
principal ideal domain In mathematics, a principal ideal domain, or PID, is an integral domain in which every ideal is principal, i.e., can be generated by a single element. More generally, a principal ideal ring is a nonzero commutative ring whose ideals are principal, ...
is an UFD. A
Euclidean domain In mathematics, more specifically in ring theory, a Euclidean domain (also called a Euclidean ring) is an integral domain that can be endowed with a Euclidean function which allows a suitable generalization of the Euclidean division of integers. ...
is an integral domain on which is defined a
Euclidean division In arithmetic, Euclidean division – or division with remainder – is the process of dividing one integer (the dividend) by another (the divisor), in a way that produces an integer quotient and a natural number remainder strictly smaller than ...
similar to that of integers. Every Euclidean domain is a principal ideal domain, and thus a UFD. In a Euclidean domain, Euclidean division allows defining a
Euclidean algorithm In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an effi ...
for computing greatest common divisors. However this does not imply the existence of a factorization algorithm. There is an explicit example of a
field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grass ...
such that there cannot exist any factorization algorithm in the Euclidean domain of the univariate polynomials over .


Ideals

In
algebraic number theory Algebraic number theory is a branch of number theory that uses the techniques of abstract algebra to study the integers, rational numbers, and their generalizations. Number-theoretic questions are expressed in terms of properties of algebraic ob ...
, the study of
Diophantine equation In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, such that the only solutions of interest are the integer ones. A linear Diophantine equation equates to a c ...
s led mathematicians, during 19th century, to introduce generalizations of the
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s called
algebraic integer In algebraic number theory, an algebraic integer is a complex number which is integral over the integers. That is, an algebraic integer is a complex root of some monic polynomial (a polynomial whose leading coefficient is 1) whose coefficients ...
s. The first
ring of algebraic integers In algebraic number theory, an algebraic integer is a complex number which is Integral element, integral over the Integer#Algebraic properties, integers. That is, an algebraic integer is a complex root of a polynomial, root of some monic polyno ...
that have been considered were
Gaussian integer In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as \mathbf /ma ...
s and Eisenstein integers, which share with usual integers the property of being
principal ideal domain In mathematics, a principal ideal domain, or PID, is an integral domain in which every ideal is principal, i.e., can be generated by a single element. More generally, a principal ideal ring is a nonzero commutative ring whose ideals are principal, ...
s, and have thus the unique factorization property. Unfortunately, it soon appeared that most rings of algebraic integers are not principal and do not have unique factorization. The simplest example is \mathbb Z
sqrt In mathematics, a square root of a number is a number such that ; in other words, a number whose ''square'' (the result of multiplying the number by itself, or  ⋅ ) is . For example, 4 and −4 are square roots of 16, because . ...
in which :9=3\cdot 3 = (2+\sqrt)(2-\sqrt), and all these factors are
irreducible In philosophy, systems theory, science, and art, emergence occurs when an entity is observed to have properties its parts do not have on their own, properties or behaviors that emerge only when the parts interact in a wider whole. Emergence ...
. This lack of unique factorization is a major difficulty for solving Diophantine equations. For example, many wrong proofs of
Fermat's Last Theorem In number theory, Fermat's Last Theorem (sometimes called Fermat's conjecture, especially in older texts) states that no three positive integers , , and satisfy the equation for any integer value of greater than 2. The cases and have been k ...
(probably including Fermat's ''"truly marvelous proof of this, which this margin is too narrow to contain"'') were based on the implicit supposition of unique factorization. This difficulty was resolved by
Dedekind Julius Wilhelm Richard Dedekind (6 October 1831 – 12 February 1916) was a German mathematician who made important contributions to number theory, abstract algebra (particularly ring theory), and the axiomatic foundations of arithmetic. His ...
, who proved that the rings of algebraic integers have unique factorization of ideals: in these rings, every ideal is a product of
prime ideal In algebra, a prime ideal is a subset of a ring that shares many important properties of a prime number in the ring of integers. The prime ideals for the integers are the sets that contain all the multiples of a given prime number, together with ...
s, and this factorization is unique up the order of the factors. The
integral domain In mathematics, specifically abstract algebra, an integral domain is a nonzero commutative ring in which the product of any two nonzero elements is nonzero. Integral domains are generalizations of the ring of integers and provide a natural set ...
s that have this unique factorization property are now called
Dedekind domain In abstract algebra, a Dedekind domain or Dedekind ring, named after Richard Dedekind, is an integral domain in which every nonzero proper ideal factors into a product of prime ideals. It can be shown that such a factorization is then necessarily ...
s. They have many nice properties that make them fundamental in algebraic number theory.


Matrices

Matrix rings are non-commutative and have no unique factorization: there are, in general, many ways of writing a
matrix Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** ''The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
as a product of matrices. Thus, the factorization problem consists of finding factors of specified types. For example, the
LU decomposition In numerical analysis and linear algebra, lower–upper (LU) decomposition or factorization factors a matrix as the product of a lower triangular matrix and an upper triangular matrix (see matrix decomposition). The product sometimes includes a pe ...
gives a matrix as the product of a
lower triangular matrix In mathematics, a triangular matrix is a special kind of square matrix. A square matrix is called if all the entries ''above'' the main diagonal are zero. Similarly, a square matrix is called if all the entries ''below'' the main diagonal are ...
by an
upper triangular matrix In mathematics, a triangular matrix is a special kind of square matrix. A square matrix is called if all the entries ''above'' the main diagonal are zero. Similarly, a square matrix is called if all the entries ''below'' the main diagonal are ...
. As this is not always possible, one generally considers the "LUP decomposition" having a
permutation matrix In mathematics, particularly in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column and 0s elsewhere. Each such matrix, say , represents a permutation of elements and, when ...
as its third factor. See
Matrix decomposition In the mathematical discipline of linear algebra, a matrix decomposition or matrix factorization is a factorization of a matrix into a product of matrices. There are many different matrix decompositions; each finds use among a particular class of ...
for the most common types of matrix factorizations. A
logical matrix A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1) matrix is a matrix with entries from the Boolean domain Such a matrix can be used to represent a binary relation between a pair of finite sets. Matrix representation ...
represents a
binary relation In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
, and
matrix multiplication In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the s ...
corresponds to
composition of relations In the mathematics of binary relations, the composition of relations is the forming of a new binary relation from two given binary relations ''R'' and ''S''. In the calculus of relations, the composition of relations is called relative multiplica ...
. Decomposition of a relation through factorization serves to profile the nature of the relation, such as a difunctional relation.


See also

*
Euler's factorization method Euler's factorization method is a technique for factoring a number by writing it as a sum of two squares in two different ways. For example the number 1000009 can be written as 1000^2 + 3^2 or as 972^2 + 235^2 and Euler's method gives the factoriz ...
for integers *
Fermat's factorization method Fermat's factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares: :N = a^2 - b^2. That difference is algebraically factorable as (a+b)(a-b); if neither factor equals one, ...
for integers *
Monoid factorisation In mathematics, a factorisation of a free monoid is a sequence of subsets of words with the property that every word in the free monoid can be written as a concatenation of elements drawn from the subsets. The Chen–Fox–Lyndon theorem states tha ...
*
Multiplicative partition In number theory, a multiplicative partition or unordered factorization of an integer ''n'' is a way of writing ''n'' as a product of integers greater than 1, treating two products as equivalent if they differ only in the ordering of the factors. Th ...
*
Table of Gaussian integer factorizations A Gaussian integer is either the zero, one of the four units (±1, ±''i''), a Gaussian prime or composite. The article is a table of Gaussian Integers followed either by an explicit factorization or followed by the label (p) if the integer is a Ga ...


Notes


References

* * * * *


External links

*
Wolfram Alpha WolframAlpha ( ) is an answer engine developed by Wolfram Research. It answers factual queries by computing answers from externally sourced data. WolframAlpha was released on May 18, 2009 and is based on Wolfram's earlier product Wolfram Mathe ...
br>can factorize too
{{Authority control Arithmetic Elementary algebra Factorization